/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 这个是符合题目要求的版本
/* 
要解决这个问题，我们需要找到数组中第 K 个最大的元素，并且要求时间复杂度为 O (n)。可以使用快速选择（Quickselect）算法来实现这一目标，该算法基于快速排序的分区思想。
方法思路
快速选择算法：
快速选择是一种选择算法，用于在未排序的数组中找到第 k 小（或第 k 大）的元素。
它与快速排序类似，但只处理包含目标元素的那一部分，因此平均时间复杂度为 O (n)。
分区操作：
选择一个基准元素（pivot），将数组分为两部分：小于等于基准的元素和大于基准的元素。
根据基准元素的位置与 k 的关系，决定继续在左半部分或右半部分查找。
第 K 个最大元素的转换：
第 K 个最大元素等价于排序后数组中索引为 n - k 的元素（其中 n 是数组长度）。
*/
var findKthLargest = function (nums, k) {
  const n = nums.length;
  const targetIndex = n - k; // 第K个最大元素的索引

  function quickSelect(left, right) {
    if (left === right) return nums[left]; // 只有一个元素

    // 分区操作
    const pivotIndex = partition(left, right);

    if (pivotIndex === targetIndex) {
      return nums[pivotIndex];
    } else if (pivotIndex < targetIndex) {
      // 在右半部分继续查找
      return quickSelect(pivotIndex + 1, right);
    } else {
      // 在左半部分继续查找
      return quickSelect(left, pivotIndex - 1);
    }
  }

  function partition(left, right) {
    const pivot = nums[right]; // 选择最后一个元素作为基准
    let storeIndex = left;

    // 将小于基准的元素交换到左边
    for (let i = left; i < right; i++) {
      if (nums[i] <= pivot) {
        [nums[i], nums[storeIndex]] = [nums[storeIndex], nums[i]];
        storeIndex++;
      }
    }

    // 将基准元素放到正确的位置
    [nums[storeIndex], nums[right]] = [nums[right], nums[storeIndex]];
    return storeIndex;
  }

  return quickSelect(0, n - 1);
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 这个是容易理解的版本
var findKthLargest = function (nums, k) {
  let newArray = nums.sort((a, b) => b - a);
  return newArray[k - 1];
};